/*
 * @lc app=leetcode.cn id=459 lang=cpp
 *
 * [459] 重复的子字符串
 */

// @lc code=start
class Solution
{
public:
  bool repeatedSubstringPattern(string s)
  {
    int n = s.size();
    char tail_c = s[n - 1];
    int len = 0;
    while (true) {
      int tail_idx = len;
      // 找到模式的最后一个字符
      while (s[tail_idx] != tail_c)
        ++tail_idx;
      len = tail_idx + 1;
      if (len > n >> 1)
        break;
      if (n % len == 0) {
        int i = len;
        for (int j = 0; i < n && s[i] == s[j]; ++i)
          j = (j + 1) % len;
        if (i == n)
          return true;
      }
    }
    return false;
  }
};
// @lc code=end
